package leetCode;

public class Q72 {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        if(m*n == 0) return m+n;

        int[][] dp = new int[m+1][n+1];
        for(int i=0;i<m+1;i++) dp[i][0] = i;
        for(int i=0;i<n+1;i++) dp[0][i] = i;

        for(int i = 1;i<m+1;i++){
            for(int j = 1;j<n+1;j++){
                int up = dp[i-1][j]+1;
                int left = dp[i][j-1]+1;
                int cor = dp[i-1][j-1];
                //因为dp的下标是字符串索引+1
                if(word1.charAt(i-1) != word2.charAt(j-1)) cor++;
                dp[i][j] = Math.min(up,Math.min(left,cor));
            }
        }

        return dp[m][n];
    }
}
